﻿#ifndef _640SEARCH_H
#define _640SEARCH_H

#endif // 640SEARCH_H

#include "virtualsearch.h"
#include <QStack>
#include <QQueue>
class Node
{
public:
    Point p;
    bool open;   //OPEN or CLOSED
    Node* next;
};

class mNode
{
public:
    Point p;
    //在每个搜索过的网格的左上、左下和右下角的位置分别标上其对应的g，h和f值；
    unsigned h, g, f;
    bool open;   //OPEN or CLOSED
    int parrent; //双亲节点/父节点
};

//typedef  struct _Stack
//{
//    Node* top;

//}Stack;

class _640Search : public VirtualSearch
{//搜索程序示例
public:
    int isFinished=0;
    _640Search(Map*map0);
    Point currentPoint;
    Node currentNode;
    int stepCount;
    //设置地图
    void setMap(Map*map0)override;
    //设置欧氏距离、曼哈顿距离和切比雪夫距离
    void setDistance(int distance0)override;
    //改变该格子的状态，改为不可走
    void changestate(Point&currentPoint)
    {
        map->changeState(currentPoint,CLOSED);
    }
protected:
    bool isPassable(Point p){
        return !map->isBlock(p)&&map->is(p)!=CLOSED;
    }
//slots:
        //单步搜索
//        void step()override;
        //连续搜索
        void DFS_Continuous();
        void BFS_Continuous();
        //终止搜索
//        void stop()override;

/*
signals:
    //单步搜索完成(成功1/失败0)
    void completed(bool);
    //全部搜索完成(成功1/失败0)
    void finished(bool);
    //输出搜索结果(要显示的节点的坐标，前驱节点坐标（不存在则为{-1，-1}），状态（OPEN、SEAL），信息（G、H、F的值）)
    void output(Point coordinate,Point pre,int flag,QString);
    //输出搜索到的路径
    void result(QVector<Point>);
    //其它输出请自行添加
*/
private:
//    int stepCount;
//    Point currentPoint;
//    int DFSpath[size][size]={0};
    QVector<QVector<int>> DFSpath;
//    int DFSdx[8] = { 1,1,0,-1,-1,-1,0,1 };
 //   int DFSdy[8] = { 0,-1,-1,-1,0,1,1,1 };
  //  int BFSdx[8] = { 1,0,-1,0,1,1,-1,-1 };
  //  int BFSdy[8] = { 0,-1,0,1,1,-1,-1,1 };
  //  Stack s;
//    Point queue[516];
//    QVector<Point> queue;
 //   int head = 0, tail = 0;
};

class DFS:public _640Search
{
private:
    int DFSdx[8] = { 1,1,0,-1,-1,-1,0,1 };
    int DFSdy[8] = { 0,-1,-1,-1,0,1,1,1 };
//    Stack s;
    QStack <Point> s;

public:
    DFS(Map *map0):_640Search(map0){};

    int DFStest(Point point, int i)
    {
        int a;
        if(map->isOutOfRange(point)) return 0;
        else
        {
            if(i==0||i==2||i==4||i==6) //移动方向为上下左右
            {
                if(isPassable(point))  //if该方向可通行
                               {
               //                    Push(s,point);
                                   s.push(point);
                               }
                else return 0; //否则返回0值
            }
            if(i==1||i==3||i==5||i==7)
            {
                Point p1,p2;
                switch(i)
                {
                case 1:{
                    p1.x=point.x;p1.y=point.y+1;
                    p2.x=point.x-1;p2.y=point.y;
                    if((map->is(p1)!=BLOCK||map->is(p2)!=BLOCK)&&map->is(point)==CLEAR) s.push(point);
                    else return 0;
                }
                case 2:{
                    p1.x=point.x;p1.y=point.y+1;
                    p2.x=point.x+1;p2.y=point.y;
                    if((map->is(p1)!=BLOCK||map->is(p2)!=BLOCK)&&map->is(point)==CLEAR) s.push(point);
                    else return 0;
                }
                case 3:{
                    p1.x=point.x;p1.y=point.y-1;
                    p2.x=point.x+1;p2.y=point.y;
                    if((map->is(p1)!=BLOCK||map->is(p2)!=BLOCK)&&map->is(point)==CLEAR) s.push(point);
                    else return 0;
                }
                case 4:{
                    p1.x=point.x;p1.y=point.y-1;
                    p2.x=point.x-1;p2.y=point.y;
                    if((map->is(p1)!=BLOCK||map->is(p2)!=BLOCK)&&map->is(point)==CLEAR) s.push(point);
                    else return 0;
                }
                }
            }
        }
    }
    //slots:
            //单步搜索
            void step()override;
            //连续搜索
            void Continuous()override;
            //终止搜索
            void stop()override;
};

class BFS:public _640Search
{
private:
    int BFSdx[8] = { 1,0,-1,0,1,1,-1,-1 };
    int BFSdy[8] = { 0,-1,0,1,1,-1,-1,1 };
//    QVector<Point> queue;
  //  int head = 0, tail = 0;
    QQueue<Node> q;

public:
    BFS(Map *map0):_640Search(map0){};
    int BFStest(Node point, int i)
    {
        int a;
        if(map->isOutOfRange(point.p)) return 0;
        else
        {
            if(i<4) //移动方向为上下左右
                       {
                           if(isPassable(point.p))  //if该方向可通行
                           {
                               q.enqueue(point);
                           }
                           else return 0; //否则返回0值
                       }
            if(i>3)  //移动方向为斜对角方向
            {
                Node p1,p2;
                switch(i)
                {
                case 4:{
                    p1.p.x=point.p.x;p1.p.y=point.p.y+1;
                    p2.p.x=point.p.x-1;p2.p.y=point.p.y;
                    if((map->is(p1.p)==CLEAR||map->is(p2.p)==CLEAR)&&map->is(point.p)==CLEAR) q.enqueue(point);
                    else return 0;
                }
                case 5:{
                    p1.p.x=point.p.x;p1.p.y=point.p.y+1;
                    p2.p.x=point.p.x+1;p2.p.y=point.p.y;
                    if((map->is(p1.p)==CLEAR||map->is(p2.p)==CLEAR)&&map->is(point.p)==CLEAR) q.enqueue(point);
                    else return 0;
                }
                case 6:{
                    p1.p.x=point.p.x;p1.p.y=point.p.y-1;
                    p2.p.x=point.p.x+1;p2.p.y=point.p.y;
                    if((map->is(p1.p)==CLEAR||map->is(p2.p)==CLEAR)&&map->is(point.p)==CLEAR) q.enqueue(point);
                    else return 0;
                }
                case 7:{
                    p1.p.x=point.p.x;p1.p.y=point.p.y-1;
                    p2.p.x=point.p.x-1;p2.p.y=point.p.y;
                    if((map->is(p1.p)==CLEAR||map->is(p2.p)==CLEAR)&&map->is(point.p)==CLEAR) q.enqueue(point);
                    else return 0;
                }
                }
            }
        }
    }
    //slots:
            //单步搜索
            void step()override;
            //连续搜索
            void Continuous()override;
            //终止搜索
            void stop()override;
};
